<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <meta name="generator" content="VuePress 2.0.0-beta.66">
    <style>
      :root {
        --c-bg: #fff;
      }
      html.dark {
        --c-bg: #22272e;
      }
      html, body {
        background-color: var(--c-bg);
      }
    </style>
    <script>
      const userMode = localStorage.getItem('vuepress-color-scheme');
			const systemDarkMode = window.matchMedia && window.matchMedia('(prefers-color-scheme: dark)').matches;
			if (userMode === 'dark' || (userMode !== 'light' && systemDarkMode)) {
				document.documentElement.classList.toggle('dark', true);
			}
    </script>
    <title>数据结构（学校） | 你好， VuePress ！</title><meta name="description" content="这是我的第一个 VuePress 站点">
    <link rel="preload" href="/assets/style-8a38cc2d.css" as="style"><link rel="stylesheet" href="/assets/style-8a38cc2d.css">
    <link rel="modulepreload" href="/assets/app-6c74e544.js"><link rel="modulepreload" href="/assets/数据结构_学校.html-cf35a9b9.js"><link rel="modulepreload" href="/assets/数据结构_学校.html-db54f988.js"><link rel="prefetch" href="/assets/index.html-75ca5b8c.js" as="script"><link rel="prefetch" href="/assets/化学.html-bcd92d03.js" as="script"><link rel="prefetch" href="/assets/IDEA.html-ce9ad873.js" as="script"><link rel="prefetch" href="/assets/python调用idm下载.html-615c23bf.js" as="script"><link rel="prefetch" href="/assets/index.html-571c49cc.js" as="script"><link rel="prefetch" href="/assets/VuePress2x搭建.html-910a2c4e.js" as="script"><link rel="prefetch" href="/assets/WindowsTerminal.html-4a75819f.js" as="script"><link rel="prefetch" href="/assets/乱七八糟.html-0ad5c8cc.js" as="script"><link rel="prefetch" href="/assets/国内访问GitHub.html-bd9bc6eb.js" as="script"><link rel="prefetch" href="/assets/虚拟机安装凤凰OS.html-fd472c84.js" as="script"><link rel="prefetch" href="/assets/软件工程过程.html-ad186a25.js" as="script"><link rel="prefetch" href="/assets/Java.html-a9e8e4b2.js" as="script"><link rel="prefetch" href="/assets/latex.html-b66b07c2.js" as="script"><link rel="prefetch" href="/assets/Markdown.html-76abef01.js" as="script"><link rel="prefetch" href="/assets/Markdown_vuepress.html-7a108572.js" as="script"><link rel="prefetch" href="/assets/Numpy.html-742cd1c8.js" as="script"><link rel="prefetch" href="/assets/python.html-80001bc2.js" as="script"><link rel="prefetch" href="/assets/python爬虫.html-0eaf5c34.js" as="script"><link rel="prefetch" href="/assets/index.html-404afaec.js" as="script"><link rel="prefetch" href="/assets/Redis.html-3c0347e6.js" as="script"><link rel="prefetch" href="/assets/Selenium.html-dd74eb14.js" as="script"><link rel="prefetch" href="/assets/快速幂算法 牛客小白月赛 1-C分元宵.html-6a00d92c.js" as="script"><link rel="prefetch" href="/assets/数据库.html-a9b825b9.js" as="script"><link rel="prefetch" href="/assets/404.html-f9875e7b.js" as="script"><link rel="prefetch" href="/assets/index.html-f9be7961.js" as="script"><link rel="prefetch" href="/assets/化学.html-55546e87.js" as="script"><link rel="prefetch" href="/assets/IDEA.html-3d6ee1dc.js" as="script"><link rel="prefetch" href="/assets/python调用idm下载.html-862a9ae4.js" as="script"><link rel="prefetch" href="/assets/index.html-71e4b30e.js" as="script"><link rel="prefetch" href="/assets/VuePress2x搭建.html-69ed53cb.js" as="script"><link rel="prefetch" href="/assets/WindowsTerminal.html-d051c0b9.js" as="script"><link rel="prefetch" href="/assets/乱七八糟.html-e6e19f4d.js" as="script"><link rel="prefetch" href="/assets/国内访问GitHub.html-5a1e283c.js" as="script"><link rel="prefetch" href="/assets/虚拟机安装凤凰OS.html-3f19c5ba.js" as="script"><link rel="prefetch" href="/assets/软件工程过程.html-d5033030.js" as="script"><link rel="prefetch" href="/assets/Java.html-07b672b0.js" as="script"><link rel="prefetch" href="/assets/latex.html-139cf75a.js" as="script"><link rel="prefetch" href="/assets/Markdown.html-24c02676.js" as="script"><link rel="prefetch" href="/assets/Markdown_vuepress.html-a9f40501.js" as="script"><link rel="prefetch" href="/assets/Numpy.html-6ea20a5f.js" as="script"><link rel="prefetch" href="/assets/python.html-da27b5e1.js" as="script"><link rel="prefetch" href="/assets/python爬虫.html-22e08aed.js" as="script"><link rel="prefetch" href="/assets/index.html-25c668e6.js" as="script"><link rel="prefetch" href="/assets/Redis.html-732c58b4.js" as="script"><link rel="prefetch" href="/assets/Selenium.html-8840df78.js" as="script"><link rel="prefetch" href="/assets/快速幂算法 牛客小白月赛 1-C分元宵.html-41e7e00f.js" as="script"><link rel="prefetch" href="/assets/数据库.html-e55ff260.js" as="script"><link rel="prefetch" href="/assets/404.html-ad53950d.js" as="script"><link rel="prefetch" href="/assets/mermaid-9e549946.js" as="script">
  </head>
  <body>
    <div id="app"><!--[--><div class="theme-container"><!--[--><header class="navbar"><div class="toggle-sidebar-button" title="toggle sidebar" aria-expanded="false" role="button" tabindex="0"><div class="icon" aria-hidden="true"><span></span><span></span><span></span></div></div><span><a href="/" class=""><img class="logo" src="/img/hero.png" alt="你好， VuePress ！"><span class="site-name can-hide">你好， VuePress ！</span></a></span><div class="navbar-items-wrapper" style=""><!--[--><!--]--><nav class="navbar-items can-hide"><!--[--><div class="navbar-item"><div class="navbar-dropdown-wrapper"><button class="navbar-dropdown-title" type="button" aria-label="编程"><span class="title">编程</span><span class="arrow down"></span></button><button class="navbar-dropdown-title-mobile" type="button" aria-label="编程"><span class="title">编程</span><span class="right arrow"></span></button><ul style="display:none;" class="navbar-dropdown"><!--[--><li class="navbar-dropdown-item"><a href="/program/Java.md" class="" aria-label="Java"><!--[--><!--]--> Java <!--[--><!--]--></a></li><li class="navbar-dropdown-item"><a href="/program/Python.md" class="" aria-label="Python"><!--[--><!--]--> Python <!--[--><!--]--></a></li><li class="navbar-dropdown-item"><!--[--><h4 class="navbar-dropdown-subtitle"><span>笔记</span></h4><ul class="navbar-dropdown-subitem-wrapper"><!--[--><li class="navbar-dropdown-subitem"><a href="/program/Markdown.html" class="" aria-label="Markdown"><!--[--><!--]--> Markdown <!--[--><!--]--></a></li><li class="navbar-dropdown-subitem"><a href="/program/latex.html" class="" aria-label="Latex"><!--[--><!--]--> Latex <!--[--><!--]--></a></li><!--]--></ul><!--]--></li><li class="navbar-dropdown-item"><a href="/program/数据库.md" class="" aria-label="数据库"><!--[--><!--]--> 数据库 <!--[--><!--]--></a></li><!--]--></ul></div></div><div class="navbar-item"><a href="/hx/化学.md" class="" aria-label="化学"><!--[--><!--]--> 化学 <!--[--><!--]--></a></div><div class="navbar-item"><a href="/others/" class="" aria-label="乱七八糟"><!--[--><!--]--> 乱七八糟 <!--[--><!--]--></a></div><div class="navbar-item"><a class="external-link" href="https://gitee.com/Francis-xsc/francis-xsc" rel="noopener noreferrer" target="_blank" aria-label="Gitee"><!--[--><!--]--> Gitee <span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!--[--><!--]--></a></div><!--]--></nav><!--[--><!--]--><button class="toggle-color-mode-button" title="toggle color mode"><svg style="" class="icon" focusable="false" viewBox="0 0 32 32"><path d="M16 12.005a4 4 0 1 1-4 4a4.005 4.005 0 0 1 4-4m0-2a6 6 0 1 0 6 6a6 6 0 0 0-6-6z" fill="currentColor"></path><path d="M5.394 6.813l1.414-1.415l3.506 3.506L8.9 10.318z" fill="currentColor"></path><path d="M2 15.005h5v2H2z" fill="currentColor"></path><path d="M5.394 25.197L8.9 21.691l1.414 1.415l-3.506 3.505z" fill="currentColor"></path><path d="M15 25.005h2v5h-2z" fill="currentColor"></path><path d="M21.687 23.106l1.414-1.415l3.506 3.506l-1.414 1.414z" fill="currentColor"></path><path d="M25 15.005h5v2h-5z" fill="currentColor"></path><path d="M21.687 8.904l3.506-3.506l1.414 1.415l-3.506 3.505z" fill="currentColor"></path><path d="M15 2.005h2v5h-2z" fill="currentColor"></path></svg><svg style="display:none;" class="icon" focusable="false" viewBox="0 0 32 32"><path d="M13.502 5.414a15.075 15.075 0 0 0 11.594 18.194a11.113 11.113 0 0 1-7.975 3.39c-.138 0-.278.005-.418 0a11.094 11.094 0 0 1-3.2-21.584M14.98 3a1.002 1.002 0 0 0-.175.016a13.096 13.096 0 0 0 1.825 25.981c.164.006.328 0 .49 0a13.072 13.072 0 0 0 10.703-5.555a1.01 1.01 0 0 0-.783-1.565A13.08 13.08 0 0 1 15.89 4.38A1.015 1.015 0 0 0 14.98 3z" fill="currentColor"></path></svg></button><!----></div></header><!--]--><div class="sidebar-mask"></div><!--[--><aside class="sidebar"><nav class="navbar-items"><!--[--><div class="navbar-item"><div class="navbar-dropdown-wrapper"><button class="navbar-dropdown-title" type="button" aria-label="编程"><span class="title">编程</span><span class="arrow down"></span></button><button class="navbar-dropdown-title-mobile" type="button" aria-label="编程"><span class="title">编程</span><span class="right arrow"></span></button><ul style="display:none;" class="navbar-dropdown"><!--[--><li class="navbar-dropdown-item"><a href="/program/Java.md" class="" aria-label="Java"><!--[--><!--]--> Java <!--[--><!--]--></a></li><li class="navbar-dropdown-item"><a href="/program/Python.md" class="" aria-label="Python"><!--[--><!--]--> Python <!--[--><!--]--></a></li><li class="navbar-dropdown-item"><!--[--><h4 class="navbar-dropdown-subtitle"><span>笔记</span></h4><ul class="navbar-dropdown-subitem-wrapper"><!--[--><li class="navbar-dropdown-subitem"><a href="/program/Markdown.html" class="" aria-label="Markdown"><!--[--><!--]--> Markdown <!--[--><!--]--></a></li><li class="navbar-dropdown-subitem"><a href="/program/latex.html" class="" aria-label="Latex"><!--[--><!--]--> Latex <!--[--><!--]--></a></li><!--]--></ul><!--]--></li><li class="navbar-dropdown-item"><a href="/program/数据库.md" class="" aria-label="数据库"><!--[--><!--]--> 数据库 <!--[--><!--]--></a></li><!--]--></ul></div></div><div class="navbar-item"><a href="/hx/化学.md" class="" aria-label="化学"><!--[--><!--]--> 化学 <!--[--><!--]--></a></div><div class="navbar-item"><a href="/others/" class="" aria-label="乱七八糟"><!--[--><!--]--> 乱七八糟 <!--[--><!--]--></a></div><div class="navbar-item"><a class="external-link" href="https://gitee.com/Francis-xsc/francis-xsc" rel="noopener noreferrer" target="_blank" aria-label="Gitee"><!--[--><!--]--> Gitee <span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!--[--><!--]--></a></div><!--]--></nav><!--[--><!--]--><ul class="sidebar-items"><!--[--><li><a href="/program/Java.md" class="sidebar-item sidebar-heading collapsible" aria-label="Java"><!--[--><!--]--> Java <!--[--><!--]--></a><!----></li><li><p tabindex="0" class="sidebar-item sidebar-heading collapsible">Python <span class="right arrow"></span></p><ul style="display:none;" class="sidebar-item-children"><!--[--><li><a href="/program/python.html" class="sidebar-item" aria-label="python-北理工"><!--[--><!--]--> python-北理工 <!--[--><!--]--></a><!----></li><!--]--></ul></li><li><p tabindex="0" class="sidebar-item sidebar-heading collapsible">Markdown <span class="right arrow"></span></p><ul style="display:none;" class="sidebar-item-children"><!--[--><li><a href="/program/Markdown.html" class="sidebar-item" aria-label="Markdown"><!--[--><!--]--> Markdown <!--[--><!--]--></a><!----></li><!--]--></ul></li><!--]--></ul><!--[--><!--]--></aside><!--]--><!--[--><main class="page"><!--[--><!--]--><div class="theme-default-content"><!--[--><!--]--><div><h1 id="数据结构-学校" tabindex="-1"><a class="header-anchor" href="#数据结构-学校" aria-hidden="true">#</a> 数据结构（学校）</h1><p>hliu@hrbust.edu.cn</p><p>wx:vinceblogger</p><p>E1126</p><p>数据挖掘与</p><p>模糊逻辑</p><h2 id="第一章-绪论" tabindex="-1"><a class="header-anchor" href="#第一章-绪论" aria-hidden="true">#</a> 第一章 绪论</h2><h3 id="数据结构的概念" tabindex="-1"><a class="header-anchor" href="#数据结构的概念" aria-hidden="true">#</a> 数据结构的概念</h3><p>对于数值计算问题的解决方法，主要是用数学方程建立数学模型</p><p>非数值计算问题，主要采用数据结构的方法建立数学模型</p><p>数据结构的研究范畴主要是非数值计算问题的操作对象及其它们之间的关系以及在计算机中的表示和实现。</p><h3 id="数据结构的基本概念" tabindex="-1"><a class="header-anchor" href="#数据结构的基本概念" aria-hidden="true">#</a> 数据结构的基本概念</h3><h4 id="数据" tabindex="-1"><a class="header-anchor" href="#数据" aria-hidden="true">#</a> 数据</h4><p>数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合</p><ul><li>数值性数据</li><li>非数值性数据</li></ul><h4 id="数据元素" tabindex="-1"><a class="header-anchor" href="#数据元素" aria-hidden="true">#</a> 数据元素</h4><ul><li>数据的基本单位。在计算机程序中常作为一个整体进行考虑和处理</li><li>有时一个数据元素可以由若干数据项(Data Item)组成。数据元素又称为元素、结点、记录</li></ul><h4 id="数据结构" tabindex="-1"><a class="header-anchor" href="#数据结构" aria-hidden="true">#</a> 数据结构</h4><p>定义：由某一数据元素的集合及该集合中所有数据元素之间的关系组成</p><p>记DataStructure= (D, S)</p><p>其中，D是某一数据元素的有限集合，S是该集合中所有数据元素之间的关系组成的有限集合</p><h4 id="数据的逻辑结构" tabindex="-1"><a class="header-anchor" href="#数据的逻辑结构" aria-hidden="true">#</a> <strong>数据的逻辑结构</strong></h4><ul><li><p>数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关</p></li><li><p>数据的逻辑结构可以看作是从具体问题抽象出来的数学模型</p></li></ul><p>数据的逻辑结构可归结为以下四类</p><ul><li>线性结 <ul><li>一对一</li><li>第一个结点无前驱</li><li>最后一个节点无后继</li></ul></li></ul><div class="language-mermaid line-numbers-mode" data-ext="mermaid"><pre class="language-mermaid"><code><span class="token keyword">graph</span> LR
A<span class="token text string">(A)</span><span class="token arrow operator">--&gt;</span>B<span class="token text string">(B)</span><span class="token arrow operator">--&gt;</span>C<span class="token text string">(C)</span><span class="token arrow operator">--&gt;</span>D<span class="token text string">(D)</span><span class="token arrow operator">--&gt;</span>E<span class="token text string">(E)</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div></div></div><ul><li><p>树形结构</p><ul><li><p>一对多</p></li><li><p>&lt;A,B&gt;有向，(C,D)无向</p></li><li></li></ul></li></ul><div class="language-mermaid line-numbers-mode" data-ext="mermaid"><pre class="language-mermaid"><code><span class="token keyword">graph</span> TD
A<span class="token text string">(A)</span>
B<span class="token text string">(B)</span>
C<span class="token text string">(C)</span>
D<span class="token text string">(D)</span>
E<span class="token text string">(E)</span>
F<span class="token text string">(F)</span>
G<span class="token text string">(G)</span>
A<span class="token arrow operator">--&gt;</span>B
A<span class="token arrow operator">--&gt;</span>C
A<span class="token arrow operator">--&gt;</span>D
C<span class="token arrow operator">--&gt;</span>E
C<span class="token arrow operator">--&gt;</span>F
E<span class="token arrow operator">--&gt;</span>G
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><ul><li>图状结构 <ul><li>多对多</li></ul></li></ul><div class="language-mermaid line-numbers-mode" data-ext="mermaid"><pre class="language-mermaid"><code><span class="token keyword">graph</span> LR
A<span class="token text string">(A)</span>
B<span class="token text string">(B)</span>
C<span class="token text string">(C)</span>
D<span class="token text string">(D)</span>
E<span class="token text string">(E)</span>
A<span class="token arrow operator">--&gt;</span>B
A<span class="token arrow operator">--&gt;</span>C
C<span class="token arrow operator">--&gt;</span>D
D<span class="token arrow operator">--&gt;</span>B
E<span class="token arrow operator">--&gt;</span>B
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><ul><li>集合结构</li></ul><div class="language-mermaid line-numbers-mode" data-ext="mermaid"><pre class="language-mermaid"><code><span class="token keyword">graph</span> TD
A<span class="token text string">(A)</span>
B<span class="token text string">(B)</span>
C<span class="token text string">(C)</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="数据的存储结构" tabindex="-1"><a class="header-anchor" href="#数据的存储结构" aria-hidden="true">#</a> 数据的存储结构</h4><ul><li>数据的存储结构是逻辑结构用计算机语言的实现</li><li>数据的存储结构依赖于计算机语言 <ul><li>顺序存储结构</li><li>链式存储结构</li></ul></li></ul><h5 id="顺序存储" tabindex="-1"><a class="header-anchor" href="#顺序存储" aria-hidden="true">#</a> 顺序存储</h5><p>所有元素存放在一片连续的存储单元中，逻辑上相邻的元素存放到计算机内存仍然相邻</p><h5 id="链式存储" tabindex="-1"><a class="header-anchor" href="#链式存储" aria-hidden="true">#</a> 链式存储</h5><p>所有元素存放在可以不连续的存储单元中，但元素之间的关系可以通过地址确定，逻辑上相邻的元素存放到计算机内存后不一定是相邻的</p><h4 id="抽象数据类型及其实现" tabindex="-1"><a class="header-anchor" href="#抽象数据类型及其实现" aria-hidden="true">#</a> 抽象数据类型及其实现</h4><ul><li><p>数据类型 一组性质相同的值的集合, 以及定义于这个值集合上的一组操作的总称</p><ul><li>构造数据类型由不同成员构成</li><li>基本数据类型可以看作是计算机中已实现的数据类型</li></ul></li><li><p>抽象数据类型 ADT: Abstract Data Type)</p><p>是指一个数学模型以及定义在此数学模型上的一组操作。</p><ul><li>两个重要特征 <ul><li>抽象性 <ul><li>用ADT描述程序处理的实体时，强调的是其本质的特征、其所能完成的功能以及它和外部用户的接口（即外界使用它的方法）</li></ul></li><li>封装性 <ul><li>将实体的外部特性和其内部实现细节分离，并且对外部用户隐藏其内部实现细节</li></ul></li></ul></li></ul></li><li><p>抽象数据类型的表示和实现</p><ul><li>抽象数据类型需要通过固有数据类型(高级编程语言中已实现的数据类型)来实现，本课程中由类模板或类来实现。</li></ul></li></ul><h3 id="算法和算法分析" tabindex="-1"><a class="header-anchor" href="#算法和算法分析" aria-hidden="true">#</a> 算法和算法分析</h3><h4 id="算法定义" tabindex="-1"><a class="header-anchor" href="#算法定义" aria-hidden="true">#</a> 算法定义</h4><p>算法是为了解决某类问题而规定的一个有限长的操作序列</p><h5 id="算法应具有的性质" tabindex="-1"><a class="header-anchor" href="#算法应具有的性质" aria-hidden="true">#</a> 算法应具有的性质</h5><ul><li>正确性</li><li>具体性</li><li>确定性</li><li>有限性</li><li>可读性</li><li>健壮性</li></ul><ol><li><p>正确性</p><p>正确性指必须完成所期望的功能，对算法是否“正确”的理解可以有如下四个层次：</p><ul><li>程序中不含任何语法错误。</li></ul><ol start="2"><li>程序对于几组输入数据能够得出满足要求的结果。</li><li>程序对于精心选择的、典型的、苛刻的并带有刁难性的几组输入数据能够得出满足要求的结果。</li><li>程序对于一切输入数据都能得出满足要求的结果。</li></ol></li><li><p>具体性</p><p>一个算法必须由一系列具体操作组成，这时的“具体”指的所有操作都必须经过已实现的基本操作有限次来实现，并且所有操作都是可读的、可执行的，每一操作必须在有限时间内完成。</p></li><li><p>确定性</p><p>算法中的所有操作都必须有确切的含义，不能产生歧义，算法的执行者或阅读者都能明确其含义及如何执行。</p></li><li><p>有限性 对于任意一组合法输入值，在执行有限步骤之后一定能结束，即：算法中的每个步骤都能在有限时间内完成</p></li><li><p>可读性</p><p>算法应具备良好的可读性，这样的算法有利于算法的查错及对算法的理解，一般算法的逻辑必须清楚、结构简单，所有标识符必须具有实际含义，能见名知义。</p></li><li><p>健壮性</p><p>健壮性指当输入数据非法时，算法能作适当的处理并作出反应，而不应死机或输出异常结果</p></li></ol><h5 id="算法描述方法" tabindex="-1"><a class="header-anchor" href="#算法描述方法" aria-hidden="true">#</a> 算法描述方法</h5><ul><li><p>用自然语言描述算法 用我们日常生活中的自然语言（可以是中文形式，也可以是英文形式）也可以描述算法</p></li><li><p>用流程图描述算法 一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。也有其他的图形辅助工具、</p></li><li><p>用其它方式描述算法</p><p>我们还可以用数学语言或约定的符号语言来描述算法</p></li><li><p>用程序设计语言描述算法</p><p>在本课中，我们将采用C++来描述算法,所有算法的描述都用C++中的函数模板或函数形式来描述</p></li></ul><h5 id="算法和程序的关系" tabindex="-1"><a class="header-anchor" href="#算法和程序的关系" aria-hidden="true">#</a> 算法和程序的关系</h5><ul><li>算法着重体现思路和方法，程序着重体现计算机的实现</li><li>程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，算法中的指令无此限制</li><li>一个算法若用计算机语言来书写，它就是一个程序</li></ul><h5 id="算法评价标准" tabindex="-1"><a class="header-anchor" href="#算法评价标准" aria-hidden="true">#</a> 算法评价标准</h5><ul><li>时间特性(时间复杂度T(n) )</li><li>空间特性(空间复杂度S(n) )</li></ul><h4 id="算法描述方法-1" tabindex="-1"><a class="header-anchor" href="#算法描述方法-1" aria-hidden="true">#</a> 算法描述方法</h4><ul><li><p>用自然语言描述算法</p><p>用我们日常生活中的自然语言（可以是中文形式，也可以是英文形式）也可以描述算法</p></li><li><p>用流程图描述算法</p><p>一个算法可以用流程图的方式来描述，输入输出、判断、处理分别用不同的框图表示，用箭头表示流程的流向。这是一种描述算法的较好方法，目前在一些高级语言程序设计中仍然采用。也有其他的图形辅助工具</p></li><li><p>用其它方式描述算法</p><p>我们还可以用数学语言或约定的符号语言来描述算法</p></li><li><p>用程序设计语言描述算法</p><p>在本课中，我们将采用C++来描述算法,所有算法的描述都用C++中的函数模板或函数形式来描述</p></li></ul><p>为表示各种状态信息，定义枚举类型StatusCode供使用，具体声明如下：</p><div class="language-txt line-numbers-mode" data-ext="txt"><pre class="language-txt"><code>// 自定义类型
enum StatusCode {
    SUCCESS, FAIL, UNDER_FLOW, 				
    OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR, 
    NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, 
    VISITED, UNVISITED
};
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="算法和程序的关系-1" tabindex="-1"><a class="header-anchor" href="#算法和程序的关系-1" aria-hidden="true">#</a> <strong>算法和程序的关系</strong></h4><ul><li>算法着重体现思路和方法，程序着重体现计算机的实现</li><li>程序不一定满足有穷性（死循环），另外，程序中的指令必须是机器可执行的，算法中的指令无此限制</li><li>一个算法若用计算机语言来书写，它就是一个程序</li></ul><h4 id="算法评价标准-1" tabindex="-1"><a class="header-anchor" href="#算法评价标准-1" aria-hidden="true">#</a> 算法评价标准</h4><ul><li>时间特性(时间复杂度T(n) )</li><li>空间特性(空间复杂度S(n) )</li></ul><h2 id="第二章-线性表" tabindex="-1"><a class="header-anchor" href="#第二章-线性表" aria-hidden="true">#</a> 第二章 线性表</h2><h3 id="线性表的逻辑结构" tabindex="-1"><a class="header-anchor" href="#线性表的逻辑结构" aria-hidden="true">#</a> 线性表的逻辑结构</h3><h4 id="线性表的定义和特点" tabindex="-1"><a class="header-anchor" href="#线性表的定义和特点" aria-hidden="true">#</a> 线性表的定义和特点</h4><h5 id="线性表的定义" tabindex="-1"><a class="header-anchor" href="#线性表的定义" aria-hidden="true">#</a> 线性表的定义</h5><p>n(≥0)个数据元素的有限序列，记作：</p><p>​ (a<sub>1</sub>,a<sub>2</sub>,...,a<sub>n</sub>)</p><p>ai是线性表中的数据元素，n是线性表长度，期中a<sub>i</sub>称为a<sub>i+1</sub>的直接前驱，简称为前驱，a<sub>i+1</sub>称为a<sub>i</sub>的直接后继，简称为后继。</p><h5 id="线性表的特点" tabindex="-1"><a class="header-anchor" href="#线性表的特点" aria-hidden="true">#</a> 线性表的特点</h5><ul><li><p>除第一个元素外，其他每一个元素有且仅有一个直接前驱</p></li><li><p>除最后一个元素外，其他每一个元素有且仅有一个直接后继</p><div class="language-mermaid line-numbers-mode" data-ext="mermaid"><pre class="language-mermaid"><code><span class="token keyword">graph</span> LR
1<span class="token arrow operator">--&gt;</span>2<span class="token arrow operator">--&gt;</span>3<span class="token arrow operator">--&gt;</span>4<span class="token arrow operator">--&gt;</span>5
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div></div></div></li></ul><h3 id="线性表的基本操作" tabindex="-1"><a class="header-anchor" href="#线性表的基本操作" aria-hidden="true">#</a> 线性表的基本操作</h3><ol><li><p>int Length() const 初始条件：线性表已存在</p><p>操作结果：返回线性表的元素个数</p></li><li><p>bool Empty() const 初始条件：线性表已存在</p><p>操作结果：如果线性表为空，则返回true，否则返回false</p></li><li><p>void Clear()</p><p>初始条件：线性表已存在。</p><p>操作结果：清空线性表。</p></li><li><p>void Traverse(void (*visit)(const ElemType &amp;)) const</p><p>初始条件：线性表已存在</p><p>操作结果：依次对线性表的每个元素调用函数(*visit)。遍历</p></li><li><p>bool GetElem(int position,ElemType &amp;e)const</p><p>初始条件：线性表已存在，1≤position≤Length() 。</p><p>操作结果：用e返回第posiiton个元素的值。</p></li><li><p>bool SetElem(int position,const ElemType &amp;e)</p><p>初始条件：线性表已存在，1≤position≤Length()。</p><p>操作结果：将线性表的position个位置的元素赋值为e。</p></li><li><p>bool Delete(int position,ElemType &amp;e)</p><p>初始条件：线性表已存在，1≤position≤Length()。</p><p>操作结果：删除线性表的第position个位置的元素，并用e返回其值，长度减1。</p></li><li><p>bool Insert(int position,const ElemType &amp;e)</p><p>初始条件：线性表已存在，1≤position≤Length()+1。</p><p>操作结果：在线性表的第position个位置钱插入e，长度加1。</p></li></ol><h3 id="线性表的顺序存储结构" tabindex="-1"><a class="header-anchor" href="#线性表的顺序存储结构" aria-hidden="true">#</a> 线性表的顺序存储结构</h3><h4 id="顺序表的定义和特点" tabindex="-1"><a class="header-anchor" href="#顺序表的定义和特点" aria-hidden="true">#</a> 顺序表的定义和特点</h4><ul><li>定义：将线性表中的元素相继存放在一个连续的存储空间中。</li><li>特点：可利用一维数组描述存储结构，采用线性表的顺序存储方式</li></ul><h4 id="顺序表的类模板的定义" tabindex="-1"><a class="header-anchor" href="#顺序表的类模板的定义" aria-hidden="true">#</a> 顺序表的类模板的定义</h4><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>// 顺序表类模板
template &lt;class ElemType&gt;
class SqList
{
protected:
	// 顺序表实现的数据成员:
	int count; 				// 元素个数
	int maxSize; 			// 顺序表最大元素个数
	ElemType *elems; 		// 元素存储空间
    // 辅助函数模板
    bool Full() const; 		// 判断线性表是否已满
    void Init(int size); 	// 初始化线性表
    public:
    // 抽象数据类型方法声明及重载编译系统默认方法声明:
    SqList(int size = DEFAULT_SIZE);// 构造函数模板
    virtual ~SqList(); 				// 析构函数模板
    int Length() const; 			// 求线性表长度
    bool Empty() const; 			// 判断线性表是否为空
    void Clear(); 					// 将线性表清空
    void Traverse(void (*visit)(const ElemType &amp;)) const; 	// 遍历线性表
    bool GetElem(int position, ElemType &amp;e) const;			// 求指定位置的元素
    bool SetElem(int position, const ElemType &amp;e);			// 设置指定位置的元素值
    bool Delete(int position, ElemType &amp;e);					// 删除元素
    bool Insert(int position, const ElemType &amp;e);			// 插入元素
    SqList(const SqList&lt;elemType&gt; &amp;copy);					// 复制构造函数模板
    SqList&lt;elemType&gt; &amp;operator =(const SqList&lt;elemType&gt; &amp;copy);	// 重载赋值运算符
};
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="顺序表辅助函数模板的实现" tabindex="-1"><a class="header-anchor" href="#顺序表辅助函数模板的实现" aria-hidden="true">#</a> 顺序表辅助函数模板的实现</h4><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>template &lt;class ElemType&gt;
bool SqList&lt;ElemType&gt;::Full() const
// 操作结果：如线性表已满，则返回true，否则返回false
{
	return count == maxSize;
}
template &lt;class ElemType&gt;
void SqList&lt;ElemType&gt;::Init(int size)
// 操作结果：初始化线性表为最大元素个数为size的空线性表
{
    maxSize = size; 					// 最大元素个数
    if (elems != NULL) delete []elems;	// 释放存储空间
    elems = new ElemType[maxSize];		// 分配存储空间
    count = 0;							// 空线性表元素个数为0
}
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="顺序表部分操作的实现" tabindex="-1"><a class="header-anchor" href="#顺序表部分操作的实现" aria-hidden="true">#</a> 顺序表部分操作的实现</h4><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>template &lt;class ElemType&gt;
SqList&lt;ElemType&gt;::SqList(int size)
// 操作结果：构造一个最大元素个数为size的空顺序表
{
    elems = NULL; 	// 未分配存储空间前,elems为空
    Init(size); 	// 初始化线性表
}

template &lt;class ElemType&gt;
SqList&lt;ElemType&gt;::~SqList()
// 操作结果：销毁线性表
{
	delete []elems; // 释放存储空间
}
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><ol><li><p>表项的插入</p><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>template &lt;class ElemType&gt;
bool SqList&lt;ElemType&gt;::Insert(int position, const ElemType &amp;e)
// 操作结果：在线性表的第position个位置前插入元
// 素e, position的取值范围为
// 1≤position≤Length()+1, 如线性表已满,则
// 返回false, 如position合法, 则返回true, 否
// 则返回false
{
    ElemType tmp;
    if (count == maxSize)
    {	// 线性表已满
   		return false;
    }
    else if (position&lt;1 || position&gt;Length()+1)
    { 	// position范围错
    	return false;
    }
    else
    { 	// 成功
        count++; // 插入后元素个数将自增1
        for (int pos = Length(); pos&gt;=position;pos--)
    	{ // 插入位置之后的元素右移
            GetElem(pos, tmp);
            SetElem(pos + 1, tmp);
  		}
        SetElem(position, e);	// 将e赋值到position位置处
        return true; 			// 插入成功
    }
}
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div></li><li><p>表项的删除</p><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>template &lt;class ElemType&gt;
bool SqList&lt;ElemType&gt;::Delete(int position, ElemType &amp;e)
// 操作结果：删除线性表的第position个位置的元素,并前用e返回其值,position的的取值范围为1≤position≤Length(),position合法时函数返回true,否则返回false
{
    ElemType tmp;
    if(position &lt; 1 || position &gt; Length())
    {	// position范围错
    	return false;
    }
    else
    { 	// position合法
   		GetElem(position, e);	// 用e返回被删除元素的值
    	for (int pos = position + 1; pos &lt;= Length();pos++)
        { 	// 被删除元素之后的元素依次左移
            GetElem(pos, tmp);
            SetElem(pos - 1, tmp);
        }
        count--; 		// 删除后元素个数将自减1
        return true;
    }
}
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div></li></ol><h4 id="顺序表的应用-集合的-差-运算" tabindex="-1"><a class="header-anchor" href="#顺序表的应用-集合的-差-运算" aria-hidden="true">#</a> 顺序表的应用：集合的“差” 运算</h4><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>// 文件路径名:s2_1\alg.h
template &lt;class ElemType&gt;
void Difference(const SqList&lt;ElemType&gt; &amp;la, const SqList&lt;ElemType&gt; &amp;lb, SqList&lt;ElemType&gt; &amp;lc)
// 操作结果: 用lc返回la和lb表示的集合的差集
// 方法: 在la中取出元素,在lb中进行查找,如果未在lb中出现了,将其插入到lc
{
    ElemType aElem, bElem;
    lc.Clear(); 		// 清空lc	
    for (int aPos = 1; aPos &lt;= la.Length(); aPos++)
    {
        la.GetElem(aPos, aElem); 		// 取出la的一个元素aElem
        bool isExist = false;			// 表示aElem是否在lb中出现
        for (int bPos = 1; bPos &lt;= lb.Length(); bPos++)
        {
            lb.GetElem(bPos, bElem);	// 取出lb的一个元素bElem
            if (aElem == bElem)
            {
                isExist = true;			// aElem同时在 la和lb中出现,置isExist为true
                break; 					// 退出内层循环
            }
        }
        if (!isExist)
        { 	// aElem在la中出现,而未在lb中未出现,将其插入到lc中
       		lc.Insert(lc.Length() + 1, aElem);
        }
    }
}
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h3 id="线性表的链式存储结构" tabindex="-1"><a class="header-anchor" href="#线性表的链式存储结构" aria-hidden="true">#</a> 线性表的链式存储结构</h3><h4 id="一、单链表-simple-linked-list" tabindex="-1"><a class="header-anchor" href="#一、单链表-simple-linked-list" aria-hidden="true">#</a> 一、单链表 (Simple Linked List)</h4><h5 id="单链表的概念" tabindex="-1"><a class="header-anchor" href="#单链表的概念" aria-hidden="true">#</a> 单链表的概念</h5><p>用一组地址任意的存储单元存放线性表中的数据元素。</p><p>以data(元素的值) + next(后继) = 结点(表示数据元素)</p><p>以“结点的序列”表示线性表称作单链表</p><p>以线性表中第一个数据元素a<sub>1</sub>的存储地址作为线性表的地址，称作线性表的头指针。</p><p>有时为了操作方便，在第一个结点之前 虚加一个“头结点”，这时指向头结点 的指针称为链表的头指针。</p><h5 id="单链表的相关类模板" tabindex="-1"><a class="header-anchor" href="#单链表的相关类模板" aria-hidden="true">#</a> 单链表的相关类模板</h5><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>// 结点类模板
template &lt;class ElemType&gt;
struct Node
{
// 数据成员:
    ElemType data;			// 数据域
    Node&lt;ElemType&gt; *next; 	// 指针域
// 构造函数模板:
    Node(); 				// 无参数的构造函数模板
    Node(ElemType item, Node&lt;ElemType&gt; *link = NULL);	// 已知数据域和指针域建立结构
};

// 简单线性链表类模板
template &lt;class ElemType&gt;
class SimpleLinkList
{
protected:
// 链表实现的数据成员:
	Node&lt;ElemType&gt; *head; // 头结点指针
// 辅助函数模板:
	Node&lt;ElemType&gt; *GetElemPtr(int position) const;	// 返回指向第position个结点的指针
	void Init(); // 初始化线性表
public:
// 抽象数据类型方法声明及重载编译系统默认方法声明:
	SimpleLinkList();								// 无参数构造函数模板
    virtual ~SimpleLinkList();						// 析构函数模板
    int Length() const; 							// 求线性表长度
    bool Empty() const;								// 判断线性表是否为空
    void Clear(); 									// 将线性表清空
    void Traverse(void (*visit)(const ElemType &amp;)) const; // 遍历线性表
    bool GetElem(int position, ElemType &amp;e)const; 	// 求指定位置的元素
    bool SetElem(int position, const ElemType&amp;e); 	// 设置指定位置的元素值
    bool Delete(int position, ElemType &amp;e);			// 删除元素
    bool Insert(int position, const ElemType &amp;e);	// 插入元素
	SimpleLinkList(const SimpleLinkList&lt;ElemType&gt;&amp;copy); // 复制构造函数模板
	SimpleLinkList&lt;ElemType&gt; &amp;operator =(const SimpleLinkList&lt;ElemType&gt; &amp;copy);// 重载赋值运算符
};
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h5 id="单链表中的插入与删除" tabindex="-1"><a class="header-anchor" href="#单链表中的插入与删除" aria-hidden="true">#</a> 单链表中的插入与删除</h5><h6 id="插入" tabindex="-1"><a class="header-anchor" href="#插入" aria-hidden="true">#</a> 插入</h6><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>newPtr = new Node&lt;ElemType&gt;(e, tmpPtr-&gt;next);
tmpPtr-&gt;next = newPtr;
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div></div></div><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>template &lt;class ElemType&gt;
bool LinkList&lt;ElemType&gt;::Insert(int position, const ElemType &amp;e)
// 操作结果：在线性表的第position个位置前插入元素e,
// position的取值范围为1≤position≤Length()+1,
// position合法时返回true, 否则返回false
{
    if (position &lt; 1 || position &gt; Length() + 1)
    { // position范围错
    	return false; // 位置不合法
    }
    else
    { // position合法
        Node&lt;ElemType&gt; *tmpPtr;
        tmpPtr = GetElemPtr(position - 1);	// 取出指向第position-1个结点的指针
        Node&lt;ElemType&gt; *newPtr;
        newPtr = new Node&lt;ElemType&gt;(e, tmpPtr-&gt;next);	// 生成新结点
        tmpPtr-&gt;next = newPtr;				// 将tmpPtr插入到链表中
        return true;
    }
}
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h6 id="删除" tabindex="-1"><a class="header-anchor" href="#删除" aria-hidden="true">#</a> 删除</h6><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>nextPtr = tmpPtr-&gt;next; 		// nextPtr为tmpPtr的后继
tmpPtr-&gt;next = nextPtr-&gt;next;	// 删除结点
delete nextPtr; 				// 释放被删结点
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>template &lt;class ElemType&gt;
bool LinkList&lt;ElemType&gt;::Delete(int position, ElemType &amp;e)
// 操作结果：删除线性表的第position个位置的元素, 并用
// e返回其值, position的取值范围为
// 1≤position≤Length(), position合法时返回true,否
// 则函数返回false
{
    if (position &lt; 1 || position &gt; Length())
    { // position范围错
   		return false;
    }
    else
    { 	// position合法
        Node&lt;ElemType&gt; *tmpPtr;
        tmpPtr = GetElemPtr(position - 1);		// 取出指向第position-1个结点的指针
        Node&lt;ElemType&gt; *nextPtr = tmpPtr-&gt;next;	// nextPtr为tmpPtr的后继
        tmpPtr-&gt;next = nextPtr-&gt;next;			// 删除结点
        e = nextPtr-&gt;data;						// 用e返回被删结点元素值
        delete nextPtr; 						// 释放被删结点
        return true;
    }
}
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="二、循环链表-circular-list" tabindex="-1"><a class="header-anchor" href="#二、循环链表-circular-list" aria-hidden="true">#</a> 二、循环链表 (Circular List)</h4><h5 id="循环链表的概念" tabindex="-1"><a class="header-anchor" href="#循环链表的概念" aria-hidden="true">#</a> 循环链表的概念</h5><ul><li>循环链表是单链表的变形。</li><li>循环链表最后一个结点的next指针不为 NULL， 而是指向了表的前端。</li><li>为简化操作，在循环链表中往往加入表头结点。</li><li>循环链表的特点是：只要知道表中某一结点的 地址，就可搜寻到所有其他结点的地址。</li></ul><h5 id="循环链表示例" tabindex="-1"><a class="header-anchor" href="#循环链表示例" aria-hidden="true">#</a> 循环链表示例</h5><h5 id="循环链表的相关类模板" tabindex="-1"><a class="header-anchor" href="#循环链表的相关类模板" aria-hidden="true">#</a> 循环链表的相关类模板</h5><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>// 简单循环链表类模板
template &lt;class ElemType&gt;
class SimpleCircLinkList
{
protected:
// 循环链表实现的数据成员:
	Node&lt;ElemType&gt; *head; // 头结点指针
// 辅助函数模板:
	Node&lt;ElemType&gt; *GetElemPtr(int position) const;	// 返回指向第position个结点的指针
	void Init(); // 初始化线性表
public:
// 抽象数据类型方法声明及重载编译系统默认方法声明:
    SimpleCircLinkList(); 			// 无参数的构造函数模板
    virtual ~SimpleCircLinkList(); 	// 析构函数模板
    int Length() const; 			// 求线性表长度
    bool Empty() const; 			// 判断线性表是否为空
    void Clear(); 					// 将线性表清空
    void Traverse(void (*visit)(const ElemType &amp;)) const; 	// 遍历线性表
    bool GetElem(int position, ElemType &amp;e) const; 			// 求指定位置的元素
    bool SetElem(int position, const ElemType &amp;e); 			// 设置指定位置的元素值
    bool Delete(int position, ElemType &amp;e); 				// 删除元素
    bool Insert(int position, const ElemType &amp;e); 			// 插入元素
    SimpleCircLinkList(const SimpleCircLinkList&lt;ElemType&gt; &amp;copy);					// 复制构造函数模板
    SimpleCircLinkList&lt;ElemType&gt; &amp;operator =(constSimpleCircLinkList&lt;ElemType&gt; &amp;copy); // 重载赋值运算符
};
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h5 id="循环链表的应用——用循环链-表求解约瑟夫问题" tabindex="-1"><a class="header-anchor" href="#循环链表的应用——用循环链-表求解约瑟夫问题" aria-hidden="true">#</a> 循环链表的应用——用循环链 表求解约瑟夫问题</h5><div class="language-txt line-numbers-mode" data-ext="txt"><pre class="language-txt"><code>约瑟夫问题的提法
n 个人围成一个圆圈，首先第1个人从1开始一个人一个人顺时针报数, 报到第m个人，令其出列。然后再从下一个人开始，从1顺时针报数，报到第m个人，再令其出列，…，如此下去, 直到圆圈中只剩一个人为止。此人即为优胜者。
例如 n = 8 m = 3
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>// 文件路径名:s2_5\alg.h
void Josephus(int n, int m)
// 操作结果:n个人围成一个圆圈，首先第1个人从1开始一
// 个人一个人顺时针报数,报到第m个人，令其出列。
// 然后再从下一个人开始，从1顺时针报数报到第m
// 个人，再令其出列，…，如此下去, 直到圆圈中只
// 剩一个人为止。此人即为优胜者
{
    SimpleCircLinkList&lt;int&gt; la; // 定义空循环链表
    int position = 0; // 报数到的人在链表中序号
    int out, winer;
    for (int k = 1; k &lt;= n; k++) la.Insert(k, k);// 建立数据域为1,2,..,n的循环链表
    cout &lt;&lt; &quot;出列者:&quot;;
    for (int i = 1; i &lt; n; i++)
    { // 循环n-1次，让n-1个个出列
    	for (int j = 1; j &lt;= m; j++)
        { // 从1报数到m
            position++;
            if (position &gt; la.Length())
            	position = 1;
    	}
    	la.Delete(position--, out);// 报数到m的人出列
   		cout &lt;&lt; out &lt;&lt; &quot; &quot;;
    }
    la.GetElem(1, winer); // 剩下的一个人为优胜者
    cout &lt;&lt; endl &lt;&lt; &quot;优胜者:&quot; &lt;&lt; winer &lt;&lt; endl;
}
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="三、双向链表-doubly-linked-list" tabindex="-1"><a class="header-anchor" href="#三、双向链表-doubly-linked-list" aria-hidden="true">#</a> 三、双向链表 (Doubly Linked List)</h4><h5 id="双向链表的概念" tabindex="-1"><a class="header-anchor" href="#双向链表的概念" aria-hidden="true">#</a> 双向链表的概念</h5><ul><li>双向链表是指在前驱和后继方向都能游历 (遍历)的线性链表。</li><li>双向链表每个结点结构：</li><li>前驱方向 ➔后继方向</li><li>双向链表通常采用带表头结点的循环链表形式。</li></ul><h5 id="双向循环链表示例" tabindex="-1"><a class="header-anchor" href="#双向循环链表示例" aria-hidden="true">#</a> 双向循环链表示例</h5><h4 id="在链表结构中保存当前位置和元素个数" tabindex="-1"><a class="header-anchor" href="#在链表结构中保存当前位置和元素个数" aria-hidden="true">#</a> 在链表结构中保存当前位置和元素个数</h4><ul><li>前面讲解了线性表的链式存储结构的实现处理简单</li><li>但许多应用程序可能要几次引用同一个数据元素，对于这类应用程序，前面的链表实现效率低下</li><li>最好在链表结构中保存当前位置和元素个数。</li></ul><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>// 线性链表类模板
template &lt;class ElemType&gt;
class LinkList
{
protected:
// 链表实现的数据成员:
    Node&lt;ElemType&gt; *head; 				// 头结点指针
    mutable int curPosition; 			// 当前位置的序号
    mutable Node&lt;ElemType&gt; * curPtr;	// 指向当前位置的指针
	int count; 							// 元素个数
// 辅助函数模板:
	Node&lt;ElemType&gt; *GetElemPtr(int position) const;// 返回指向第position个结点的指针
	void Init(); // 初始化线性表
public:
// 抽象数据类型方法声明及重载编译系统默认方法声明:
    LinkList(); 				// 无参数的构造函数模板
    virtual ~LinkList(); 		// 析构函数模板
    int Length() const; 		// 求线性表长度
    bool Empty() const; 		// 判断线性表是否为空
    void Clear(); 				// 将线性表清空
    void Traverse(void (*visit)( const ElemType &amp;)) const; 	// 遍历线性表
    bool GetElem(int position, ElemType &amp;e) const; 		// 求指定位置的元素
    bool SetElem(int position, const ElemType &amp;e);  	// 设置指定位置的元素值
    bool Delete(int position, ElemType &amp;e); 			// 删除元素
    bool Insert(int position, const ElemType &amp;e); 		// 插入元素
    LinkList(const LinkList&lt;ElemType&gt; &amp;copy);			// 复制构造函数模板
    LinkList&lt;ElemType&gt; &amp;operator =(const LinkList&lt;ElemType&gt; &amp;copy);	// 重载赋值运算符
};
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h4 id="实例研究——-一元多项式的表示" tabindex="-1"><a class="header-anchor" href="#实例研究——-一元多项式的表示" aria-hidden="true">#</a> 实例研究—— 一元多项式的表示</h4><p>一元多项式</p><p>p<sub>n</sub>(x) = p<sub>0</sub> + p<sub>1</sub>x + p<sub>2</sub>x<sup>2</sup> + ... + p<sub>n</sub>x<sup>n</sup></p><p>在计算机中，可以用一个线性表来表示:</p><p>P = (p<sub>0</sub> , p<sub>1</sub> , …，p<sub>n</sub> )</p><p>但是对于形如 S(x) = 1 + 3x<sup>10000</sup> – 2x<sup>20000</sup> 的多项式，上述表示方法是否合适？</p><p>一般情况下的一元稀疏多项式可写成</p><p>P<sub>n</sub> (x) = p<sub>1</sub>x<sup>e1</sup> + p<sub>2</sub>x<sup>e2</sup> + ┄ + p<sub>m</sub>x<sup>em</sup></p><p>其中：p<sub>i</sub> 是指数为e<sub>i</sub> 的项的非零系数， 0≤ e<sub>1</sub> &lt; e<sub>2</sub>&lt; ┄ &lt; e<sub>m</sub> = n</p><p>可以下列线性表表示：</p><p>（（p<sub>1</sub> , e<sub>1</sub>）, (p<sub>2</sub> , e<sub>2</sub> ), ┄, (p<sub>m</sub>,e<sub>m</sub>) ）</p><p>例如：</p><p>P<sub>999</sub>(x) = 7x<sup>3</sup> - 2x<sup>12</sup> - 8x<sup>999</sup></p><p>可用线性表</p><p>( (7, 3), (-2, 12), (-8, 999) )</p><p>表示</p><div class="language-c++ line-numbers-mode" data-ext="c++"><pre class="language-c++"><code>// 多项式项类
struct PolyItem
{
// 数据成员:
    double coef; 	// 系数
    int expn;		// 指数
// 构造函数:
    PolyItem() ; 	// 无数据的构造函数
    PolyItem(double cf, int en);// 已知系数域和指数域建立结构
};
// 多项式类
class Polynomial
{
protected:
// 多项式实现的数据成员:
	LinkList&lt;PolyItem&gt; polyList;	// 多项式组成的线性表
public:
    // 抽象数据类型方法声明:
    Polynomial(){}; 		// 无参构造函数
    ~Polynomial(){}; 		// 析构函数
    int Length() const; 	// 求多项式的项数
    bool IsZero() const; 	// 判断多项式是否为0
    void SetZero(); 		// 将多项式置为0
    void Display(); 		// 显示多项式
    void InsItem( const PolyItem &amp;item);				// 插入一项
    Polynomial operator +(const Polynomial &amp;p) const; 	// 加法运算符重载
    Polynomial operator -(const Polynomial &amp;p) const; 	// 减法运算符重载
    Polynomial operator *(const Polynomial &amp;p) const; 	// 乘法运算符重载
    Polynomial(const Polynomial &amp;copy); 				// 复制构造函数
    Polynomial(const LinkList&lt;PolyItem&gt; &amp;copyLinkList);	// 由多项式组成的线性表构造多项式
    Polynomial &amp;operator =(const Polynomial &amp;copy); 	// 重载赋值运算符
    Polynomial &amp;operator =(const LinkList&lt;PolyItem&gt; &amp;copyLinkList); // 重载赋值运算符
};
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div></div><!--[--><!--]--></div><footer class="page-meta"><div class="meta-item edit-link"><a class="external-link meta-item-label" href="https://gitee.com/Francis-xsc/francis-xsc/edit/main/program/数据结构_学校.md" rel="noopener noreferrer" target="_blank" aria-label="Edit this page"><!--[--><!--]--> Edit this page <span><svg class="external-link-icon" xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path><polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg><span class="external-link-icon-sr-only">open in new window</span></span><!--[--><!--]--></a></div><div class="meta-item last-updated"><span class="meta-item-label">最后更新时间: </span><!----></div><div class="meta-item contributors"><span class="meta-item-label">Contributors: </span><span class="meta-item-info"><!--[--><!--[--><span class="contributor" title="email: 920364365@qq.com">Francis-xsc</span><!----><!--]--><!--]--></span></div></footer><!----><!--[--><!--]--></main><!--]--></div><!----><!--]--></div>
    <script type="module" src="/assets/app-6c74e544.js" defer></script>
  </body>
</html>
